package leetcode_en

import (
	"fmt"
	"go-study/src/leetcode"
	"strconv"
)

// 1837. Sum of Digits in Base K
func sumBase(n int, k int) (sum int) {
	for ; n > 0; n = n / k {
		sum += n % k
	}
	return
}

//897. Increasing Order Search Tree递归
func increasingBST(root *leetcode.TreeNode) *leetcode.TreeNode {
	return recurveLeft(root, nil)
}
func recurveLeft(root *leetcode.TreeNode, tail *leetcode.TreeNode) *leetcode.TreeNode {
	if root == nil {
		return tail
	}
	var res = recurveLeft(root.Left, root)
	root.Left = nil
	root.Right = recurveLeft(root.Right, tail)
	return res
}

/*
1. Two Sum
*/
func twoSum(nums []int, target int) []int {
	// key:数，value：下标
	var existed = make(map[int]int)
	for i, num := range nums {
		if value, ok := existed[target-num]; ok {
			return []int{value, i}
		} else {
			existed[num] = i
		}
	}
	return nil
}

/*
2. Add Two Numbers
*/
func addTwoNumbers(l1 *leetcode.ListNode, l2 *leetcode.ListNode) *leetcode.ListNode {
	var curNode *leetcode.ListNode = &leetcode.ListNode{0, nil}
	var res = curNode
	var take, l1Value, l2Value int
	for l1 != nil || l2 != nil {
		l1Value = 0
		l2Value = 0
		if l1 != nil {
			l1Value = l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			l2Value = l2.Val
			l2 = l2.Next
		}
		var sum = l1Value + l2Value + take
		var cur = sum % 10
		take = sum / 10
		var next = &leetcode.ListNode{cur, nil}
		curNode.Next = next
		curNode = next

	}
	if take > 0 {
		var next = &leetcode.ListNode{1, nil}
		curNode.Next = next
	}
	return res.Next
}

/*
3. Longest Substring Without Repeating Characters
*/
func lengthOfLongestSubstring(s string) int {
	var left, right, max, len int = 0, 0, 0, len(s)
	exist := make(map[byte]bool)
	for left < len && right < len {
		if _, ok := exist[s[right]]; !ok {
			exist[s[right]] = true
			right++
			max = maxNum(max, right-left)
		} else {
			delete(exist, s[left])
			left++
		}
	}
	return max
}

func maxNum(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/*
4. Median of Two Sorted Arrays
*/
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	arr := []int{}

	for len(nums1) > 0 || len(nums2) > 0 {
		var n int

		if len(nums1) == 0 {
			n = nums2[0]
			nums2 = nums2[1:]
		} else if len(nums2) == 0 {
			n = nums1[0]
			nums1 = nums1[1:]
		} else {
			if nums1[0] > nums2[0] {
				n = nums2[0]
				nums2 = nums2[1:]
			} else {
				n = nums1[0]
				nums1 = nums1[1:]
			}
		}

		arr = append(arr, n)
	}

	l := len(arr)

	if l%2 == 0 {
		return float64(arr[l/2]+arr[l/2-1]) / 2
	} else {
		return float64(arr[l/2])
	}
}

/**
 * @description: 111. Minimum Depth of Binary Tree
	Given a binary tree, find its minimum depth.
	The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
	Note: A leaf is a node with no children.
 * @return: 最浅深度
 * @author: kami
 * @关键词：层序遍历，使用队列，GO中没有队列，使用切片模拟
 * @date: 2021/7/3 14:09
*/
func minDepth(root *leetcode.TreeNode) int {
	if root == nil {
		return 0
	}
	var minDepth = 1
	var queue = make([]*leetcode.TreeNode, 1)
	queue[0] = root
	var curIndex = 0
	for {
		var size = len(queue)
		for i := curIndex; i < size; i++ {
			if queue[i].Left == nil && queue[i].Right == nil {
				return minDepth
			}
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
			}
		}
		minDepth++
		curIndex = size
	}

}

/**
 * @description: 112. Path Sum
	Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that
	adding up all the values along the path equals targetSum.
	A leaf is a node with no children.
 * @return: 是否有一条路径节点之和等于目标值
 * @author: kami
 * @关键词：回溯
 * @date: 2021/7/5 9:26
*/
func hasPathSum(root *leetcode.TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	if root.Val == targetSum && root.Left == nil && root.Right == nil {
		return true
	}
	targetSum -= root.Val
	return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum)
}

/**
 * @description: 113. Path Sum II
	Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum.

	A leaf is a node with no children.
 * @return: 所有路径节点之和等于目标值
 * @author: kami
 * @关键词：妙啊
 * @date: 2021/7/6 7:55
*/
func pathSum(root *leetcode.TreeNode, sum int) [][]int {
	var slice [][]int
	slice = findPath(root, sum, slice, []int(nil))
	return slice
}

func findPath(n *leetcode.TreeNode, sum int, slice [][]int, stack []int) [][]int {
	if n == nil {
		return slice
	}
	sum -= n.Val
	stack = append(stack, n.Val)

	if sum == 0 && n.Left == nil && n.Right == nil {
		slice = append(slice, append([]int(nil), stack...))
		stack = stack[:len(stack)-1]
	}

	slice = findPath(n.Left, sum, slice, stack)
	slice = findPath(n.Right, sum, slice, stack)
	return slice
}

/*
9. Palindrome Number
*/
func isPalindrome(x int) bool {
	if x < 0 {
		return false
	}
	if x < 10 {
		return true
	}
	strX := strconv.Itoa(x)
	size := len(strX)
	for i := 0; i < size/2; i++ {
		if strX[i] != strX[size-1-i] {
			return false
		}
	}
	return true
}

/*
13. Roman to Integer
*/
func romanToInt(s string) int {
	sMap := map[byte]int{
		'I': 1,
		'V': 5,
		'X': 10,
		'L': 50,
		'C': 100,
		'D': 500,
		'M': 1000,
	}
	size := len(s)
	var sum = sMap[s[size-1]]
	var nextMax = sum
	for i := size - 2; i >= 0; i-- {
		var curInt = sMap[s[i]]
		if curInt >= nextMax {
			sum += curInt
			nextMax = curInt
		} else {
			sum -= curInt
		}
	}
	return sum
}

/*
14. Longest Common Prefix
*/
func longestCommonPrefix(strs []string) string {
	var curPrefix = strs[0]
	size := len(strs)
	for i := 1; i < size; i++ {
		minSize := len(curPrefix)
		curStrSize := len(strs[i])
		if minSize > curStrSize {
			minSize = curStrSize
		}
		var isNotCut = true
		//["flower","flow","flight"]
		for j := 0; j < minSize; j++ {
			fmt.Println("i = ", i, ", j = ", j, ", curPrefix = ", curPrefix, ", strs[i] = ", strs[i])
			if curPrefix[j] != strs[i][j] {
				curPrefix = curPrefix[0:j]
				isNotCut = false
				break
			}
		}
		if isNotCut {
			curPrefix = curPrefix[0:minSize]
		}
	}
	return curPrefix
}

/*
20. Valid Parentheses
使用栈的数据结构，但是go中没有栈，使用切片应该也可以
*/
func isValid(s string) bool {
	stack := make([]byte, 0)
	for _, val := range s {
		switch val {
		case '(':
			stack = append(stack, '(')
		case ')':
			size := len(stack)
			if size == 0 {
				return false
			}
			if stack[size-1] == '(' {
				if size == 1 {
					stack = nil
				} else {
					stack = stack[0 : size-1]
				}
			} else {
				return false
			}
		case '{':
			stack = append(stack, '{')
		case '}':
			size := len(stack)
			if size == 0 {
				return false
			}
			if stack[size-1] == '{' {
				if size == 1 {
					stack = nil
				} else {
					stack = stack[0 : size-1]
				}
			} else {
				return false
			}
		case '[':
			stack = append(stack, '[')
		case ']':
			size := len(stack)
			if size == 0 {
				return false
			}
			if stack[size-1] == '[' {
				if size == 1 {
					stack = nil
				} else {
					stack = stack[0 : size-1]
				}
			} else {
				return false
			}
		default:
			return false
		}
	}
	return len(stack) == 0
}

/*
21. Merge Two Sorted Lists
*/
func mergeTwoLists(list1 *leetcode.ListNode, list2 *leetcode.ListNode) *leetcode.ListNode {
	cur1Node := list1
	cur2Node := list2
	var curRes = &leetcode.ListNode{}
	resHead := curRes
	for cur1Node != nil && cur2Node != nil {
		if cur1Node.Val > cur2Node.Val {
			curRes.Next = cur2Node
			cur2Node = cur2Node.Next
		} else {
			curRes.Next = cur1Node
			cur1Node = cur1Node.Next
		}
		curRes = curRes.Next
	}
	if cur1Node != nil {
		curRes.Next = cur1Node
	}
	if cur2Node != nil {
		curRes.Next = cur2Node
	}

	return resHead.Next
}

/*
26. Remove Duplicates from Sorted Array
*/
func removeDuplicates(nums []int) int {
	size := len(nums)
	if size == 0 {
		return 0
	}
	cnt := 1
	pre := 0
	for i := 1; i < size; i++ {
		if nums[i] != nums[pre] {
			nums[pre+1] = nums[i]
			pre++
			cnt++
		}
	}

	return cnt
}

/*
27. Remove Element
*/
func removeElement(nums []int, val int) int {
	size := len(nums)
	if size == 0 {
		return 0
	}
	if size == 1 && nums[0] == val {
		return 0
	}
	cnt := 0
	for i := 0; i < size; i++ {
		if nums[i] != val {
			nums[cnt] = nums[i]
			cnt++
		}

	}

	return cnt

}

/*
28. Implement strStr()
*/
func strStr(haystack string, needle string) int {
	size1 := len(haystack)
	size2 := len(needle)
	if size2 == 0 {
		return 0
	}
	if size2 > size1 {
		return -1
	}
	diff := size1 - size2 + 1
	for i := 0; i < diff; i++ {
		cur := i
		for j := 0; j < size2; j++ {
			if haystack[cur] != needle[j] {
				break
			}
			cur++
		}
		if cur-i == size2 {
			return i
		}

	}
	return -1
}

/*
35. Search Insert Position
*/
func searchInsert(nums []int, target int) int {
	size := len(nums)
	if target < nums[0] {
		return 0
	}
	if target > nums[size-1] {
		return size
	}
	var leftIdx = 0
	var rightIdx = size
	var midIdx = size / 2
	for target != nums[midIdx] {

		if target < nums[midIdx] {
			if target > nums[midIdx-1] {
				return midIdx
			}
			rightIdx = midIdx
		} else {
			if target < nums[midIdx+1] {
				return midIdx + 1
			}
			leftIdx = midIdx
		}
		midIdx = (leftIdx + rightIdx) / 2
	}
	return midIdx
}

/*
53. Maximum Subarray
*/
func maxSubArray(nums []int) int {
	max, sum := nums[0], nums[0]
	for _, v := range nums[1:] {
		if sum < 0 {
			sum = v
		} else {
			sum += v
		}
		if max < sum {
			max = sum
		}
	}
	return max
}

/*
58. Length of Last Word
*/
func lengthOfLastWord(s string) int {
	size := len(s)
	var space = true
	var cnt = 0
	for i := size - 1; i >= 0; i-- {
		if space {
			if s[i] != ' ' {
				space = false
				cnt += 1
			}
		} else {
			if s[i] != ' ' {
				cnt += 1
			} else {
				return cnt
			}
		}
	}
	return cnt
}

/*
66. Plus One
*/
func plusOne(digits []int) []int {
	size := len(digits)
	carry := 0
	if digits[size-1]+1 < 10 {
		digits[size-1] += 1
		return digits
	} else {
		digits[size-1] = 0
		carry = 1
	}
	for i := size - 2; i >= 0; i-- {
		if carry > 0 {
			digits[i] += 1
		}

		if digits[i] >= 10 {
			carry = 1
			digits[i] = 0
		} else {
			carry = 0
			break
		}
	}
	if carry > 0 {
		digits = append([]int{1}, digits...)
	}
	return digits
}

/*
144. Binary Tree Preorder Traversal
前序遍历-》中，左，右
递归
*/
func preorderTraversal(root *leetcode.TreeNode) []int {
	if root != nil {
		res := make([]int, 0)
		return recursiveDfs(root, TraversalOrderPre, res)
	}
	return []int{}
}

/*
145. Binary Tree Postorder Traversal
后序遍历-》左，右，中
*/
func postorderTraversal(root *leetcode.TreeNode) []int {
	if root != nil {
		res := make([]int, 0)
		return recursiveDfs(root, TraversalOrderBack, res)
	}
	return []int{}
}

type TraversalOrderEnum int

const (
	TraversalOrderPre  TraversalOrderEnum = 1
	TraversalOrderMid  TraversalOrderEnum = 2
	TraversalOrderBack TraversalOrderEnum = 3
)

func recursiveDfs(t *leetcode.TreeNode, order TraversalOrderEnum, a []int) []int {
	switch order {
	case TraversalOrderPre:
		a = append(a, t.Val)
		if t.Left != nil {
			a = recursiveDfs(t.Left, TraversalOrderPre, a)
		}
		if t.Right != nil {
			a = recursiveDfs(t.Right, TraversalOrderPre, a)
		}
	case TraversalOrderMid:

		if t.Left != nil {
			a = recursiveDfs(t.Left, TraversalOrderMid, a)
		}
		a = append(a, t.Val)
		if t.Right != nil {
			a = recursiveDfs(t.Right, TraversalOrderMid, a)
		}
	case TraversalOrderBack:
		if t.Left != nil {
			a = recursiveDfs(t.Left, TraversalOrderBack, a)
		}
		if t.Right != nil {
			a = recursiveDfs(t.Right, TraversalOrderBack, a)
		}
		a = append(a, t.Val)
	}

	return a
}

/*
167. Two Sum II - Input Array Is Sorted
*/
func twoSum167(numbers []int, target int) []int {
	// key:target-curVal期望值，curIdx当前下标
	expectMap := make(map[int]int)
	// 最小期望值
	minExpectVal := numbers[0]
	size := len(numbers)
	for i := 0; i < size; i++ {
		if minExpectVal > numbers[i] {
			return []int{}
		}
		if val, ok := expectMap[numbers[i]]; ok {
			return []int{val + 1, i + 1}
		}
		expectVal := target - numbers[i]
		expectMap[expectVal] = i
		if expectVal < minExpectVal {
			minExpectVal = expectVal
		}
	}
	return []int{}
}

/*

 */
/**
 * @Description: 168. Excel Sheet Column Title
 * 跟之前一家外企telenav的面试题一样
 * @Keyword: 26进制
 * @Author: kami
 * @Date: 2021/12/9 23:18
 **/
func convertToTitle(columnNumber int) string {
	if columnNumber <= 26 {
		str := 'A' + columnNumber - 1
		return string(rune(str))
	}
	str := make([]byte, 27)
	str[1] = 'A'
	for i := 2; i < 27; i++ {
		str[i] = str[i-1] + 1
	}
	var main = columnNumber
	var res string
	for main > 26 {
		left := main % 26
		if left == 0 {
			left = 26
			main -= 1
		}
		main = main / 26
		res = string(str[left]) + res
	}

	return string(str[main]) + res
}

/**
 * @Description: 203. Remove Linked List Elements
 * @Keyword: 前后指针记录
 * @Author: kami
 * @Date: 2021/12/10 22:34
 **/
func removeElements(head *leetcode.ListNode, val int) *leetcode.ListNode {
	// 过滤首位是val的节点
	dumyHead := &leetcode.ListNode{
		Next: head,
	}
	curNode := head
	preNode := dumyHead
	for curNode != nil {
		if curNode.Val == val {
			preNode.Next = curNode.Next
		} else {
			preNode = curNode
		}

		curNode = curNode.Next
	}

	return dumyHead.Next
}

/**
 * @Description: 205. Isomorphic Strings
 * @Keyword: 重复位置要重复，单独位置要单独
 * @Author: kami
 * @Date: 2021/12/10 23:12
 **/
func isIsomorphic(s string, t string) bool {
	mutiS := make(map[byte]int)
	mutiT := make(map[byte]int)
	for i, val := range s {
		if idx, ok := mutiS[byte(val)]; ok {
			if t[i] != t[idx] {
				return false
			}
		} else {
			if _, ok1 := mutiT[t[i]]; ok1 {
				return false
			}
			mutiS[byte(val)] = i
		}

		if idx, ok := mutiT[t[i]]; !ok {
			mutiT[t[i]] = idx
		}
	}
	return true
}
